package lc279;

public class Lc279_1 {

    /**
     * 暴力破解
     * dp解题思路：
     * 1、明确状态值，这里因为从n开始，也就是最大数开始，所以状态值count只需要大于n即可
     * 2、明确选择，也就是最小值的定义。这里因为是平方数，所以下一个n，那应该就是当前n-平方数，也就是n-i*i，然后+1，和当前去的状态去比较，获取最小值
     * 3、处理异常情况，例如n==0,则直接return 0 根据题目，初始n，至少是1，又因为for循环的情况下，i * i <= n ，所以1-1*1 也就是0，那直接return即可
     * 4、最后return count即可
     * time：O(n*n)
     * space: O(1)
     * spend: 60m
     */
    public int numSquares(int n) {
        return numSquaresHelper(n);

    }

    private int numSquaresHelper(int n) {
        // base case
        if(n == 0){
            return 0;
        }
        // 状态
        int count = n + 1;
        for(int i = 1; i * i <= n; i++){
            // 选择
            count = Math.min(count, numSquaresHelper(n - i * i) + 1);
        }

        return count;
    }

}
